#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

class Solution {
public:
    string sortSentence(string s) {
        vector<string> v(9);
        string tmp;
        int n = 0;
        for (auto& ch : s)
        {
            if (ch >= '1' && ch <= '9')
            {
                v[ch - '0' - 1] = tmp;
                tmp.clear();
                ++n;
            }
            else if (ch != ' ')
            {
                tmp.push_back(ch);
            }
        }
        string ans = v[0];
        for (int i = 1; i < n; ++i)
        {
            ans += " " + v[i];
        }
        return ans;
    }

    int mySqrt(int x) {
        if (x == 1) return 1;
        if (x == 0) return 0;
        int left = 1, right = x >> 1;
        while (left < right)
        {
            int m = left + ((right - left + 1) >> 1);
            if (pow(m, 2) > x) right = m - 1;
            else if (pow(m, 2) <= x) left = m;
        }
        return left;
    }

    int findLHS(vector<int>& nums) {
        unordered_map<int, int> hash;
        int res = 0;
        for (int num : nums)
        {
            ++hash[num];
        }
        for (auto& kv : hash)
        {
            if (hash.count(kv.first + 1))
                res = max(res, kv.second + hash[kv.first + 1]);
        }
        return res;
    }

    long pre = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;
        auto left = isValidBST(root->left);
        if (left == false) return false;
        if (root->val > pre) pre = root->val;
        else return false;
        auto right = isValidBST(root->right);
        return left && right;
    }
};
